import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * Created by Jin on 2017/5/2.
 */
public class ConsistentHash {


    public static String[] servers = {
            "192.168.1.110",
            "192.168.1.111",
            "192.168.1.112",
            "192.168.1.113",
            "192.168.1.114",
            "192.168.1.115",
            "192.168.1.116",
            "192.168.1.117",
            "192.168.1.118",
            "192.168.1.119"};

    private static List<String> realNodes = new LinkedList<>();

    private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();

    private static SortedMap<Integer, String> subMap ;

    private static final int VIRTUAL_NODES = 10;

    public static ConsistentHash consistentHash;

    public static ConsistentHash getInstance(){
        if (consistentHash == null){
            synchronized (ConsistentHash.class){
                if (consistentHash ==null){
                    consistentHash = new ConsistentHash();
                }
            }
        }

        return consistentHash;
    }


    static {
        // 先把原始的服务器添加到真实结点列表中
        for (int i = 0; i < servers.length; i++) {
            realNodes.add(servers[i]);
        }
        // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
        for (String node:realNodes) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                String virtaulNode = node+"&&VN"+ i;
                int hash = getHash(virtaulNode);
                virtualNodes.put(hash,virtaulNode);
                System.out.println("虚拟节点[" + virtaulNode + "]被添加, hash值为" + hash);
            }
        }
    }

    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
     */
    public static int getHash(String node) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < node.length(); i++)
            hash = (hash ^ node.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        // 如果算出来的值为负数则取其绝对值
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }

    /**
     * 得到应当路由到的结点
     * @param object 存放的对象
     * @return
     */
    public static String getServer(String object){
        // 得到带路由的结点的Hash值
        int hash = getHash(object);
        // 得到大于该Hash值的所有Map
        subMap = virtualNodes.tailMap(hash);
        // 第一个Key就是顺时针过去离node最近的那个结点
        Integer rNode = subMap.isEmpty()?virtualNodes.firstKey():subMap.firstKey();
        // 返回对应的虚拟节点名称，这里字符串稍微截取一下
        String virtualnode = virtualNodes.get(rNode);
        return virtualnode.substring(0,virtualnode.indexOf("&&"));


    }

    /**
     * 另一种实现
     * @param object
     * @return
     */
    public static String getServerName(String object){
        int hash = getHash(object);
        subMap = virtualNodes.tailMap(hash);
        String virtualnode;
        if (subMap.isEmpty()){
            Integer rNode = virtualNodes.firstKey();
            virtualnode = virtualNodes.get(rNode);
        }else{
            Integer rNode = subMap.firstKey();
            virtualnode = subMap.get(rNode);
        }

        return virtualnode.substring(0,virtualnode.indexOf("&&"));
    }
}
